package com.syedu.day13.homework1;

import java.util.ArrayList;
import java.util.List;

/**
 * description：
 * 对于不同的字符串，我们希望能有办法判断相似程度，我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法如下：
 * 1 修改一个字符，如把“a”替换为“b”。
 * 2 增加一个字符，如把“abdd”变为“aebdd”。
 * 3 删除一个字符，如把“travelling”变为“traveling”。
 * 比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加和减少一个“g”的方式来达到目的。上面的两种方案，都只需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离＋1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度为1/2=0.5.
 * 给定任意两个字符串，你是否能写出一个算法来计算出它们的相似度呢？
 *
 *  算法思路：
 *  1、将字符串转为字符数组，然后将字符数据转换为List集合，使用其contains判断是否包含
 *  2、包含这说明该字符不需要操作，不包含说明要删除此字符。用两变量存储包含的字符个数和需要要删除的个数
 *  3、用第一个字符串个数减去包含的字符个数，得到需要增加的字符个数，在加上需要删除的字符串个数。
 *  4、按照字符串的相似度,相似度等于“距离＋1”的倒数公式计算。
 */
public class StringDistance {
    public static void main(String[] args) {
        double result = calculateStringDistance("abc", "abcdef");
        System.out.println(result);
    }

    /**
     * 计算字符串相似度
     * @param expressionA   字符串A
     * @param expressionB   字符串B
     * @return 相似度结果
     */
    public static double calculateStringDistance(String expressionA, String expressionB) {
        double result = 0.0;
        List<Character> listA = toList(expressionA);
        List<Character> listB = toList(expressionB);
        int countA = 0, countB = 0;
        for (int i = 0; i < listB.size(); i++) {
            if (listA.contains(listB.get(i))) {
                countA += 1;
            } else {
                countB += 1;
            }
        }
        int total = listA.size() - countA + countB + 1;
        if (total > 0) {
            result = 1.0/total;
        }
        System.out.println(expressionA + "和" + expressionB + "的相似度为:" + result);
        return result;
    }

    private static List<Character> toList(String str) {
        List<Character> characterList = new ArrayList<>();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            characterList.add(chars[i]);
        }
        return characterList;
    }
}